//给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充
//。
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X"
//,"X"]]
//输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
//解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都
//会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
// 
//
// 示例 2： 
//
// 
//输入：board = [["X"]]
//输出：[["X"]]
// 
//
// 
//
// 提示： 
//
// 
// m == board.length 
// n == board[i].length 
// 1 <= m, n <= 200 
// board[i][j] 为 'X' 或 'O' 
// 
// 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 
// 👍 557 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

public class SurroundedRegions {
    public static void main(String[] args) {
        Solution solution = new SurroundedRegions().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void solve(char[][] board) {
//            for (int i = 0; i < board.length; i++) {
//                for (int j = 0; j < board[0].length; j++) {
//                    if (board[i][j] == 'O') {
//                        boolean res = dfs(i, j, board);
//                        if(res){
//                            dfs2(i,j,board);
//                        }
//                    }
//                }
//            }
            for (int i = 0; i < board.length; i++) {
                if (board[i][0]=='O'){
                    dfs3(i,0,board);
                }
                if (board[i][board[0].length-1]=='O'){
                    dfs3(i,board[0].length-1,board);
                }
            }
            for (int i = 0; i < board[0].length; i++) {
                if (board[0][i]=='O'){
                    dfs3(0,i,board);
                }
                if (board[board.length-1][i]=='O'){
                    dfs3(board.length-1,i,board);
                }
            }
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j]='X';
                    }
                    if (board[i][j] == '1') {
                        board[i][j]='O';
                    }
                }
            }

        }
        private void dfs3(int i, int j, char[][] board) {
            if (i<0 || j<0 || i>=board.length || j>=board[0].length || board[i][j]!='O'){
                return;
            }

            board[i][j]='1';
            dfs3(i-1,j,board);
            dfs3(i,j-1,board);
            dfs3(i+1,j,board);
            dfs3(i,j+1,board);

        }
        private boolean dfs(int i, int j, char[][] board) {
            if (i<0 || j<0 || i>=board.length || j>=board[0].length){
                return false;
            }
            if (board[i][j]=='X'){
                return true;
            }
            board[i][j]='X';
            boolean res = dfs(i-1,j,board) && dfs(i,j-1,board) && dfs(i+1,j,board) && dfs(i,j+1,board);

            board[i][j]='O';

            return res;

        }
        private boolean dfs2(int i, int j, char[][] board) {
            if (i<0 || j<0 || i>=board.length || j>=board[0].length){
                return false;
            }
            if (board[i][j]=='X'){
                return true;
            }
            board[i][j]='X';
            boolean res = dfs2(i-1,j,board) && dfs2(i,j-1,board) && dfs2(i+1,j,board) && dfs2(i,j+1,board);

//            board[i][j]='O';

            return res;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}